Along with prevalence of camera-equipped mobile phones, the demand for a service using a camera not only as a device for simply shooting pictures but also as an input device. For example, there is known a service of ordering a product or presenting relevant information by shooting a product shown in a magazine, a catalog, or the like. For such a purpose, it is necessary to recognize an object in an image at a high speed and with a high accuracy.
The inventors have already proposed a method for recognizing an image at a high speed and with a high accuracy from a large-scale image database (see, for example, Patent Literature 1, Non-Patent Literatures 2 and 3). In the method, PCA-SIFT (see, for example, Non-Patent Literature 1) is used for local features representing the local characteristics of an image, local features of a query are compared with local features in an image database by using approximate nearest neighbor search, and an image that is the closest to the query is determined as a recognition result. It is noted that normally, a local feature is represented as a vector, as is the case in PCA-SIFT. Features of the methods of Patent Literature 1 and Non-Patent Literature 2 are cascading processing in which the degree of approximation is adjusted as appropriate in accordance with a query image to increase the speed of processing. A feature of the method of Non-Patent Literature 3 is reduction of a used amount of memory by using scalar quantization.